package month1;

public class CopyListWithRandomPointer138_04 {
    public static void main(String[] args) {
        System.out.println(copyRandomList(new Node(1)));
    }

    static Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Node tmp = head;
        while(tmp != null) {
            Node next = tmp.next;
            tmp.next = new Node(tmp.val);
            tmp.next.next = next;
            tmp = next;
        }
        tmp = head;
        while(tmp != null) {
            if (tmp.random != null) {
                tmp.next.random = tmp.random.next;
            }
            tmp = tmp.next.next;
        }
        Node ret = head.next;
        tmp = head;
        while(tmp.next != null) {
            Node next = tmp.next;
            tmp.next = tmp.next.next;
            tmp = next;
        }
        return ret;
    }
}
